#include <stdio.h>
#include <stdlib.h>

/**  
 * 定义链表节点的结构体  
 */  
typedef struct Node {  
    int data;  
    struct Node* pre;  
    struct Node* next;  
} Node;  
  
/**  
 * 初始化链表  
 * @return 链表头节点的指针  
 */  
Node* initList() {  
    Node* L = (Node*)malloc(sizeof(Node));  
    if (L == NULL) {  
        return NULL; // 分配内存失败，返回NULL  
    }  
    L->data = 0; // 通常头节点的数据字段不存储有效数据，可忽略或用于计数  
    L->pre = L;  
    L->next = L; // 链表头尾相连，形成循环链表  
    return L;  
}  
  
/**  
 * 在链表头部插入元素  
 * @param L 链表头节点的指针  
 * @param data 要插入的数据  
 */  
void headInsert(Node* L, int data) {  
    if (L == NULL) {  
        return; // 链表为空，无法插入  
    }  
    Node* node = (Node*)malloc(sizeof(Node));  
    if (node == NULL) {  
        return; // 分配内存失败，无法插入  
    }  
    node->data = data;  
    node->next = L->next;  
    node->pre = L;  
    L->next->pre = node;  
    L->next = node;  
    // L->data++; // 头节点数据不用于计数，此行代码应该去掉  
}  
  
/**  
 * 在链表尾部插入元素  
 * @param L 链表头节点的指针  
 * @param data 要插入的数据  
 */  
void tailInsert(Node* L, int data) {  
    if (L == NULL) {  
        return; // 链表为空，无法插入  
    }  
    Node* node = (Node*)malloc(sizeof(Node));  
    if (node == NULL) {  
        return; // 分配内存失败，无法插入  
    }  
    node->data = data;  
    Node* tail = L->pre; // tail指向链表最后一个节点  
    node->pre = tail;  
    node->next = L;  
    tail->next = node;  
    L->pre = node;  
    // L->data++; // 头节点数据不用于计数，此行代码应该去掉  
}  
  
/**  
 * 删除链表中的元素  
 * @param L 链表头节点的指针  
 * @param data 要删除的数据  
 * @return 成功删除的标记（1为成功，0为失败）  
 */  
int delete(Node* L, int data) {  
    if (L == NULL || L->next == L) {  
        return 0; // 链表为空或只有一个节点，无需删除  
    }  
    Node* node = L->next;  
    while (node != L) {  
        if (node->data == data) {  
            node->pre->next = node->next;  
            node->next->pre = node->pre;  
            free(node);  
            // L->data--; // 头节点数据不用于计数，此行代码应该去掉  
            return 1;  
        }  
        node = node->next;  
    }  
    return 0;  
}

/**
 * print all items in a link list
 * @param L the head pointer of link list
 */
void printList(Node* L) {
    Node* node = L->next;
    while (node != L) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

/**
 * main function
 * @return null
 */
int main() {
    Node* L = initList();
    headInsert(L, 1);
    headInsert(L, 2);
    headInsert(L, 4);
    headInsert(L, 5);
    printList(L);
    tailInsert(L, 6);
    tailInsert(L, 7);
    printList(L);
    delete (L, 7);
    printList(L);
    return 0;
}